Computer networks create powerful environments for the search and retrieval of distributed information. However, due to bandwidth limitations, computer networks are often not suited for interactively browsing large amounts of data. As a result, retrieving and displaying large images can be a slow process. Image compression is effective in reducing the amount of data for storing and transmitting images, however, most image compression algorithms are optimized for rate and distortion performance rather than to facilitate interactive image retrieval. The interactive retrieval of large images is a form of browsing in which the views of portions of the image data are successively retrieved in a drill-down or roll-up fashion.
Hierarchical data structures such as the wavelet packet tree, as taught by Coifman, et al. [Coifman, et al., 92], and the spatial quad-tree, as taught by Samet [Samet, 84], can be used to decompose the images into a hierarchies of views. They use tree-based data structures to arrange the views of the image data into parent-child dependency relationships. The views of the images can be generated by decomposing the parent elements or by synthesizing together the children elements. Coifman, et al. taught a method for selecting the view elements in the wavelet packet tree in order to represent the image data completely and without information loss. Similar methods can be applied to the spatial quad-tree for representing the image data by a complete set of spatial segments.
In the wavelet packet tree, the view elements correspond to various spatial-frequency subbands. In particular, some of these subbands correspond to low-resolution views of the image data. However, none of the view elements in the wavelet packet tree correspond to spatial segments of the image data On the other hand, the view elements in the spatial quad-tree correspond to various spatial segments of the image data, but only at full resolution.
The spatial quad-tree and wavelet packet tree can be integrated in a graph data structure as taught by Smith and Chang [Smith and Chang, 97]. The view elements in the space and frequency graph correspond to the spatial segments of the various spatial-frequency subbands. Some of the view elements in the space and frequency graph correspond to the spatial segments of the low-resolution views of the image data. Smith and Chang developed a method for selecting the view elements in the space and frequency graph in order to optimize the compression of the image data in terms of rate-distortion performance. The method decomposes the image data into a redundant set of view elements, assigns each view element a compression cost and selects a complete and non-redundant set of view elements based on the compression costs. The selected view elements can be used to reconstruct the image data.
However, Smith and Chang did not explore the use of the space and frequency graph for accessing or constructing the segmented multi-resolution views of the image data needed by applications that involve the interactive retrieval of the images.
The Flashpix image format has been used for progressively retrieving large images over the Internet using the Internet Imaging Protocol. The user-applications compose views of the images by retrieving tiles from the Flashpix files at the server [Eastman Kodak Co. 1996]. In order to speedup the retrieval of multi-resolution image views, the Flashpix-based servers store multiple versions of the image at different scales, which results in a redundancy of information of 133% [Burt and Adelson 1983]. The Flashpix format is also capable of storing the image non-redundantly, but, it then requires added processing to extract the image views. In both cases, the Flashpix-based systems do not reuse data at the client to reduce data transmission in drill-down or roll-up browsing.
There is benefit in storing the images in forms that allow the images to be rapidly browsed and retrieved by remote client applications in a drill-down fashion. Furthermore, there is added benefit of storing the data in a compressed form without adversely impacting the speed at which the image views are extracted or generated.